Logic Blog 2016

Editor: Andr\'e Nies

1. Westrick: randomness and rotations of the unit circle

The following result was obtained at the computability retreat at Research Centre Coromandel in February. It started through discussions between Adam Day, Andre Nies, Dan Turetsky and Brown Westrick.

\vsp

Let $P\sub[0,1]$ be a $\Pi^0_1$ class. \begin{thm} Let $X \in MLR$. Let $k\in \NN$. 1. There is a rational number $q \neq 0$ such that for all $i\leq k$, $X + qi \in P$. 2. Let $\alpha$ be a computable irrational number. There is an integer $n \neq 0$ such that for all $i\leq k$, $(X + \alpha n i \mod 1) \in P$. \end{thm} \begin{proof}

Both (1) and (2) are proved by the same method. Dynamically construct a Solovay test as follows. Put the empty string $\estring$ in the test. Then for any $\sigma$ that has been placed in the test, let $r_\sigma$ be a rational number (for (1)) or let $n_\sigma \gt 0$ be an integer (for (2)) such that \bc $\frac{2^{-|\sigma|}}{2k+3} \lt r_\sigma, (\alpha n_\sigma \mod 1) \lt \frac{2^{-|\sigma|}}{2k+2}$. \ec These bounds are chosen so that for every $z \in [\sigma]$, $z + kr_\sigma \in [\sigma]$ or $z - kr_\sigma \in [\sigma]$. Let $U_s$ denote the complement of $P$ as seen at stage $s$. We will enumerate $\tau$ into the test at stage $s$ if we see the following occur: 1. $\sigma \prec \tau$, 2. $\tau$ is incomparable with any $\tau'$ which has already entered the test on the basis of this same $\sigma$ 3. $[\tau] \cap U_s = \emptyset$ 4. For some integer $i \in [-k, k]$, $[\tau] + i r_\sigma \subseteq [\sigma]\cap U_s$. The point is to enumerate $[\tau]$ if its potential $\pm r_\sigma$ $k$-recurrence inside $[\sigma]$ is invalidated. For (2), replace $r_\sigma$ everywhere with $\alpha n_\sigma \mod 1$.

The test catches any $z\in P$ which fails to $k$-recur for all $r \in \mathbb{Q}\setminus \{0\}$ (resp. for all $\alpha n$ with $n \in \mathbb{Z}\setminus \{0\}$). We need to show it is a Solovay test.

We show that for every $\sigma$ in the test, the total measure of all $\tau$ added to the test as a result of $\sigma$ is at most $\frac{2k+2}{2k+3} \mu [\sigma]$. So if the depth of $\tau$ is the number of initial segments that $\tau$ has in the test, then $\mu(\cup\{[\tau] : \tau \text{ of depth } d\}) \leq \left(\frac{2k+2}{2k+3}\right)^d$, so this will suffice to show that the total measure of the test is finite.

When $\sigma$ is first put in the test, $[\sigma]$ is disjoint from $U_s$. When first $\rho$ enters $U_s$ with $\sigma \prec \rho$, we can consider $[\sigma]$ as being divided into two parts, both invariant under addition of $r_\sigma$: $C=\{z \in [\sigma] : z + ir_\sigma \in [\rho]$ for some $i \in \mathbb{Z}\}$, and its complement. All $z$ whose initial segments could potentially be enumerated as a result of $\rho$ are contained in $C$. Also $[\rho]\subseteq C$, but nothing comparable with $\rho$ will be enumerated. By the choice of $r_\sigma$, $\frac{\mu[\rho]}{\mu C} \leq \frac{1}{2k+3}$. Therefore, the measure added to the test as a result of the addition of $\rho$, and as a result of the addition of any future $\rho'$ with $[\rho'] \subseteq C$, is bounded by $\frac{2k+2}{2k+3}\mu C$.

The remaining set $[\sigma] \setminus C$ is currently untouched but may in the future be seen to intersect the complement of $P$. When that happens, we apply the same reasoning inside of $[\sigma]\setminus C$, partitioning it into two invariant pieces and arguing that one piece remains untouched, while the other can never contribute more than $\frac{2k+2}{2k+3}$ of its measure to the test. Continuing in this way, we get the desired bound on the measure the test uses in response to $\sigma$. \end{proof}

2. Nies: alternative proof of Thm.\ \ref{thm:multiple recurrence

(1)}

The case $k=1$ of the theorem can be derived from a result of Figueira et al.\ ¹⁴; also see \cite[3.3.7]{Nies:book}. That theorem of ¹⁴ says that if $X$ is not autoreducible, then there is a bit position $n$ such that the bit $n$ is indifferent for $X$ with respect to $P$, which means that we can change $X$ at $n$ and remain in $P$. This change corresponds to adding or subtracting the rational $\tp{-n}$.

Now let us obtain an arithmetical progression namely $X + qi \in P$ for $i \lt k/2$ (for technical reasons).

At first we work with $Z\in k^\omega$. Extending the case of $k=2$, we say that $Z$ is auto-reducible if there is a reduction procedure $\Phi$ such that $\Phi^Z(n) \neq Z(n)$ for each $n$, and the computation $\Phi^Z(n)$ only queries the oracle at values other than $n$. As before, one checks that a ML-random sequence $Z$ is not auto-reducible. We say that position $n$ is indifferent for $Z$ with respect to a $\PI 1$ class $P\sub k^\omega$ if we can change $Z$ at $n$ to any value $\lt k$ and remain in $P$.

\begin{prop} Let $Q\sub k^\omega$ be a $\PPI$ class. If $Z \in Q$ is not autoreducible, then there is a position $n$ such that the bit $n$ is indifferent for $Z$ with respect to $Q$. \end{prop} \begin{proof} A straightforward extension of the argument for $k=2$. If there is no such position, given input $n$ the reduction $\Phi$ searches for a stage $s$ and $i \lt k$ such that $Z$, with position $n$ changed to value $i$, is not in $Q$, and once found, output this $i$. \end{proof}

To obtain the arithmetical progression assume that $k= \tp r$ for $r \in \NN$. Given $\PPI$ class $P \sub \cantor$ and ML-random $X\in P$ , let $Q$, $Z$ be the class/sequence rewritten using the alphabet $0, \ldots, k-1$. That is, the block bits of $X$ in positions $nr \ldots (n+1)r -1$ corresponds the symbol of $Z$ in position $n$. If $n$ is indifferent for $Z$ in $Q$, then we have an arithmetical progression $X + qi\in P$, where $i \lt k/2$, $q = \pm \tp{-rn}$.

\part{Randomness via algorithmic tests}

3. Smart sets for arbitrary cost functions

\newcommand{\conc}{\hat{\,\,}}

\newcommand{\cost}{\mathbf{c}} \newcommand{\dost}{\mathbf{d}} \newcommand{\cc}{\mathbf{c}} \newcommand{\limcost}{\underline{\cost}} \newcommand{\converge}{\!\!\downarrow}

\newcommand \sinit {s_{\mathrm{init}}}

The following is work of Greenberg, Miller, Nies and Turetsky at RCC in Feb.\ 2015, and in Wellington slightly later. For background on cost functions see ³⁰. In the following all cost functions satisfy the limit condition $\lim_x \cost(x) = 0$.

\begin{definition}[³] Let $\cost$ be a cost function. A descending sequence \seq{V_n} of uniformly c.e.\ open sets is a $\cost$-bounded test if $\leb(V_n) =O( \limcost(n))$ for all $n$. \end{definition} We think of each $V_n$ as an approximation for $Y\in \bigcap_k V_k$. Being in $\bigcap_n V_n$ can be viewed as a new sense of obeying $\cost$ that makes sense for ML-random sets. \begin{lemma} Suppose $aY$ fails a $\cost$-bounded test $\bigcap_n V_n$ where $a \in \{0,1\}$. Then $Y$ fails a $\cost$-bounded test. \end{lemma}

\begin{proof} We may suppose $a=0$ and $X \in V_n$ implies $X(0) =0$. Since $\leb T (V_n )\le 2 \leb V_n$ where $T$ is the usual shift operator on Cantor space, $\seq{ T (V_n)}$ is also a $\cost$-bounded test. Clearly $Y$ fails it. \end{proof}

The basic motivating result is a generalisation in terms of cost functions of a fact of Hirschfeldt and Miller. \begin{prop} If $A \models \cost$ and $Y$ is a ML-random captured by a $\cost$-bounded test, then $A \leT Y$. \end{prop}

The most powerful kind of set obeying a given cost function

Informally, if $A$ is smart for $\cost$ then $A$ is as complex as possible among the sets obeying $\cost$, in the sense that the only random sets $Y$ above $A$ are the ones that have to be there because $A$ obeys the cost function that puts it below $Y$ anyway.

\begin{theorem} Let $\cost$ be a cost function with $\cost \to \cost_\Omega$. Some c.e.\ set $A$ is smart for $\cost$. \end{theorem}

\begin{proof} Recall $\Upsilon$ is a ``universal" Turing functional in the sense that $\Upsilon({0^e1}\conc{X}) = \Phi_e(X)$ for each $X,e$. We build $A$ and a $\cost$-test \seq{\+ U_k} capturing any ML-random $Y$ such that $A = \Upsilon^Y$. This suffices for the theorem by Lemma~ ?.

Since $2^{-x}\le^\times \Omega - \Omega_x$, we may assume that $\cost(x,s) \ge \tp{-x}$ for $x \le s$.

As in ³, during the construction of $A$ we build a global ``error set":

\[ \+ E_s = \{ Y \colon \ex n\, [ \Upsilon^Y_s(n)\converge=0 \lland A_s(n) = 1 ]\}\]

All all stages $s$ we will have \[ \tag{$\diamond$} \leb \+ U_{k,s} \le \cost(k,s) + \leb ( \+ E_{s+1} - \+ E_k). \] So since $\leb (\+ E - \+ E_k) \le^\times \cost_ \Omega(k)$ and $\cost_\Omega(k) \le^\times\limcost(k)$, the test \seq{\+ U_k} is indeed a $\cost$-test.

We reserve the interval $I_k = [\tp k, \tp{k+1} )$ for ensuring ($\diamond$). The construction of $\+ U_k$ is as follows. At stage $s \gt k$, let $x = \min (I_k - A_{s-1})$. Let \[ \+ U_{k,s} = \bigcup_{t$\diamond$) threatens to fail at $s$, namely $\leb \+ U_{k,s} \gt \cost(k,s) + \leb ( \+ E_s - \+ E_k)$, put $x$ into $A_{s+1}$. This causes $\+ U_{k,s}$ to go into $\+ E_{s+1}$.

First we verify that $x$ always exists, that is, we enumerate at most $\tp k$ times for $\+ U_k$. If we do this at stage $s$, $\leb\+ U_{k,s} \gt 2^{-k} + \leb(\+ E_s - \+E_k)$. Since $\+U_{k,s} \cap \+E_k = \emptyset$ by definition, and $\+U_{k,s} \subseteq \+E_{s+1}$, it follows that $\leb(\+E_{s+1} - \+E_s) \gt 2^{-k}$. Since $\leb \+E \le 1$, this can happen at most $2^k$ times.

In particular, if $A = \Upsilon^Z$ then $Z \in \bigcap_k \+ U_k$. It remains to verify that $A \models \cost$. If we enumerate $x$ for $\+ U_k$ at stage $s$ then \[ \leb (\+ U_{k,s} - \+ E_s) = \leb (\+ U_{k,s} - (\+ E_s - \+ E_k) ) \ge \leb (\+ U_{k,s} ) - \leb(\+ E_s - \+ E_k) > \cost(k,s ) \ge \cost (x,s). \] Since $\+ U_{k,s} - \+ E_s \sub \+ E_{s+1} - \+ E_s$, we see that $\cost(x,s) \lt \leb(\+E_{s+1} - \+E_s)$. This implies that the total cost of the enumeration of $A$ is at most $1$. \end{proof}

ML-reducibility

\begin{definition} Let $\cost$ be a cost function and $A$ be a $\DII$ set. We say that $A$ is ML-complete for $\cost$ if $A \models \cost$, and $\fa B \, [B \models \cost \RA B \le_{ML} A]$. \end{definition} \begin{cor} $A$ is smart for $\cost$ $\LR$ $A$ is ML-complete for $\cost$. \end{cor} \begin{proof} $\RA$: Suppose $A\leT Y$ for ML-random $Y$. Then some $\cost$-bounded test captures $Y$. If $B \models \cost$, then $B \leT Y$ by the basic fact~ ?. Thus $B \le_{ML} A$ as required.

\noindent $\LA$: By Theorem~ ? let $\wt A$ be smart for $\cost$. Suppose $A \leT Y$ for ML-random $Y$; we want to show that $Y$ is captured by a $\cost$-bounded test. Since $A$ is ML-complete for $\cost$ we have $\wt A \le_{ML} A$, so $\wt A \leT Y$, so $Y$ is captured by a $\cost$-bounded test as required. \end{proof} In particular, the ML-degree of a smart set $A$ for $\cost$ is uniquely determined by $\cost$. On the other hand, for each low c.e.\ set $A$ there is a c.e.\ set $B \not \le_T A$ such that $B \models \cost$ \cite[5.3.22]{Nies:book}. If $A$ is smart for $\cost$, then $A \oplus B$ is also smart for $\cost$. As each $K$-trivial is low, the Turing degree of a set $A$ that is smart for $\cost$ is not uniquely determined by $\cost$.

\begin{question} Given $\cost$ can we build a smart for $\cost$ set $A$ that is cappable? Can we even have two smart for $\cost$ sets that form a minimal pair? \end{question}

The strongest cost function obeyed by a given set

Recall that $T(A)$ is the shift of $A$. \begin{thm} For each cost function $\dost$, there is a cost function $\cost \ge \dost$ and a c.e.\ set $A$ such that $A \models \cost$ and $T(A) \not \models \cost$. \end{thm} Since $\cost_A \to \cost$, this shows that $T(A) \not \models \cost_A$. \begin{proof} We fix a listing \seq{\Phi_e} of all (possibly partial) computable enumerations \seq{B_t}, where $B_t \simeq D_{\Phi_e(t)}$ and $D_{\Phi_e(t)} \sub D_{\Phi_e(t+1)}$ if defined. We may assume $\dost(s-1, s) \ge \tp{-s}$. We define $\cost(x,s)$ so that $\cost(x,s) \ge \dost(x,s)$ for each $x,s$. At a stage $x$ of the construction we may also declare that $\cost(x-1,x) \ge \alpha$, which by monotonicity entails that $\cost(y, s) \ge \alpha$ for each $y<x$ and $s \ge x$. We meet the requirements

\[R_e \colon \, T(A) = \bigcup_t D_{\Phi_e(t)} \RA \cost \seq {\Phi_e} \ge 1. \] The strategy for $R_e$ tries to ensure $\limcost (x-1)$ is large and $\limcost(x)$ is small for sufficiently many $x$. In that case $R_e$ can put $x$ into $A$ for the small cost, while the opponent's enumeration \seq{\Phi_e} of $T(A)$ has to deal with the large cost. One problems in implementing this idea is the timing as we will of $\Phi_e (u)$ for a stage $u$ only at a stage $s$ much larger than $u$. Also we always have $\cost(x,s) \ge \dost(x,s)$, so once we discover that the enumeration of $x$ would help because \seq{\Phi_e} caught up sufficiently much, it may be that the enumeration of $x$ has become too expensive for $R_e$. Similar to the usual construction of a set obeying $\dost$, in this case we simply pick a new $x$. Since $\dost$ has the limit condition, eventually we will always be able to keep $x$. At a stage $s \gt 0$ let $s_{\init}(e)$ be the greatest stage $t\lt s$ such that $t=0$ or $R_e$ has been initialised at $t$. If by stage $s$ the strategy for $R_e$ has been initialised for $b$ times it can spend a $\cost$-cost of $\tp{-b-e}$ in enumerating $A$. It is also allowed to raise $\cost(x,s)$ to $\tp{-\sinit(e)}$. The $e$-expansionary stages are the ones at which \seq {\Phi_e} catches up with $T(A)$. We declare $0$ as $e$-expansionary. A stage $s>0$ is $e$-expansionary if for the largest $e$-expansionary stage $t<s$, we have that $T(A_s)\uhr{t+2} = \Phi_{e,s}(u) \uhr {t+2}$ where $u$ is largest such that $\Phi_{e,s}(u)$ is defined and $u>t$. \noindent Strategy for $R_e$. Write $\alpha = \tp{-\sinit(e)}$. A rational parameter $\gamma_e \in [0,1]$ measures progress of $R_e$. We set $\gamma_e$ to $0$ when $R_e$ is initialised. At $e$-expansionary stage $s$, if $\gamma_e \le 1$ do the following. Initialize lower priority requirements. Declare that $\cost (s-1,s+1) \ge \alpha$. (So for $\Phi_e$, changing at $s-1$ will be expensive after stage $s$.) Let $x \lt s$ be the last $e$-expansionary stage. If $\dost(x,s) \lt \tp{-b-e} \alpha$, put $x$ into $A_{s}$ (note that no-one has raised the $\cost$ cost for $x$ above $\dost(x,s)$ yet), add $\alpha$ to $\gamma_e$. Say that $R_e$ acts.

Clearly $R_e$ only acts $\tp{\sinit(e)}= 1/\alpha$ times while it is not initialised. \begin{claim} $A \models \cost$. \end{claim} When $R_e$ acts at $s$ we have $\cost(x,s)\le \tp{-b-e} \alpha$ by initialisation. \begin{claim} $TA \not \models \cost$. \end{claim} Otherwise $TA \models \cost$ via some enumeration \seq {\Phi_e} such that \cost \seq {\Phi_e} \lt 1. Since $\dost$ satisfies the limit condition, $\gamma_e$ reaches the value $1$. This is at least what \seq {\Phi_e} pays for the enumerations of $x-1$ into $TA$. For when $R_e$ acts at $s$ via $x$ then $x-1 \not \in \Phi_e(u)$ for some $u>x$ since $s$ is $e$-expansionary. By the next $e$-expansionary stage we have $x-1 \in \Phi_e(u')$ for some $u' \gt u$. So $\Phi_e$ paid the cost $\cost(x-1,x+1) \ge \alpha$ that was set by $R_e$ at stage $x$. \end{proof}

\part{Computability theory}

4. Merkle, Nies and Stephan: A dual of the Gamma question

Merkle, Nies and Stephan worked at NUS in February. They considered a dual of the $\Gamma$ operator on Turing degrees.

For $Z\sub \NN$ the lower density is defined to be

Recall that

which only depends on the Turing degree of $A$. The $\Gamma$ operator was introduced by Andrews, Cai, Diamondstone, Jockusch and Lempp ¹. \begin{definition}

\end{definition} Intuitively, \bi \item $\Gamma(A)$ measures how well computable sets can approximate the sets that $A$ computes, counting the asymptotically worst case (the infimum over all $Y \le_T A$). In contrast, \item $\Delta(A)$ measures how well the sets that $A$ computes can approximate the computable sets, counting the asymptotically best case (the supremum over all $Y \le_T A$). \ei Clearly the maximum value of $\Delta(A)$ is $1/2$. The operator $\Delta(A)$ is related to the analog of a cardinal characteristic introduced by Brendle and Nies in the 2015 Logic Blog~¹². They define $\+ B(\sim_p)$ to be the class of oracles $A$ that compute a set $Y$ such that for each computable set $X$, we have $\ul \rho (X \lra Y) \gt p$. For each $p$ with $0 \le p \lt 1/2$, \bc $\Delta(A) \gt p \RA A \in \+ B(\sim_p) \RA \Delta(A) \ge p$. \ec We state three minor results. \begin{prop} Let $A$ be 2-generic. Then $\Delta(A)=0$. \end{prop} A proof is given at the end of Section~Section 2.

\begin{prop} Let $A$ compute a Schnorr random $Y$. Then $\Delta(A) = 1/2$. \end{prop} This is clear because $\underline \rho(Y\leftrightarrow R)=1/2$ for each computable $R$.

\begin{prop} Let $p\in (0,1/2)$ be computable. Let $A$ be Schnorr random for the Bernoulli measure w.r.t.\ $p$. Then $\delta(B) =p$ for each $B \equiv_1 A$. \end{prop}

The ``$\Delta$-question" is (or rather, was, and has been quite short-lived):

\begin{question}[solved] Can $\Delta(A)$ be properly between $0$ and $1/2$? \end{question} Using a dual form of Monin's technique's below, this has been answered in the negative by Nies; see Section~Section 2.

5. Monin - A resolution of the Gamma question

We show that there is no sequence $X$ with a Gamma value strictly between $0$ and $1/2$.

\begin{definition} For a given $n \in \omega$ and two strings $\s_1, \s_2 \in 2^n$, the notation $d(\s_1, \s_2)$ denotes the normalised hamming distance between $\s_1$ and $\s_2$, that is, the number of bits on which $\s_1$ and $\s_2$ differ divided by $n$. \end{definition}

\begin{definition} Let $F:\omega \rightarrow \omega$ be a function. Given a function $f$ such that $f(n)\lt 2^{F(n)}$, for each $n$, by $[f(n)]$ we denote the string of length $F(n)$ encoded by $f(n)$. \end{definition}

The following weakens the notion of infinitely often equal (i.o.e.) for a computable bound, which was first studied in ²⁹. \begin{definition} Let $F:\omega \rightarrow \omega$ be a function and $\alpha \in [0,1]$. A function $f$ is $2^{F(n)}$-infinitely often $\alpha$-equal if for every computable function $g:\omega \rightarrow \omega$ which is bounded by $2^{F(n)}$, we have:

Informally, we want $f$ to equal infinitely often on a fraction of at least $\alpha$ bits, to every computable function bounded by $2^{F(n)}$. Typically we will have $\alpha \gt 1/2$.

\end{definition}

\begin{proposition} Let $1/2 \lt \alpha \lt 1$. Suppose that for no $k$, $X$ computes a function which is $2^{\lfloor 2^{n/k} \rfloor}$-i.o.$\alpha$-e. Then $\Gamma(X) \geq 1 - \alpha$. \end{proposition} \begin{proof} Consider any sequence $Y$ computed by $X$. Fix some $c \in \omega$ and let $k$ be the smallest integer such that $2^{1/k} - 1 \lt 1/(2c)$. We then split $Y$ in blocks of bits of length $\lfloor 2^{n/k} \rfloor$. We now argue that for $n$ large enough, the number of bits in the $n+1$-th block is smaller than $1/c$ times the sum of the number of bits in the previous blocks. By the sum of geometric series we have:

which implies that

For $n$ large enough we have $\frac{1}{2} \sum_{i=0}^{i \leq n} 2^{i/k} \gt (n+c)$. Thus for $n$ large enough we have:

We then have for $n$ large enough that:

Thus the length of the $n+1$ block of bit is smaller than $1/c$ of the sum of the length of the previous blocks.

Define the function $f \lt 2^{\lfloor 2^{n/k} \rfloor}$ by setting $f(n)$ to the value coded by the bits of the $n$-th block. Suppose that $f$ is not $2^{\lfloor 2^{n/k} \rfloor}$ i.o.$\alpha$-e. In particular there must be some computable function $h \leq 2^{\lfloor 2^{n/k} \rfloor}$ such that for almost every $n$, $[h(n)]$ agrees with $[f(n)]$ on a fraction of strictly less than $\alpha$ bits. Let $h'$ be defined as the complement of $h$ bitwise. Then for almost every $n$, $[h'(n)]$ agrees with $[f(n)]$ on a fraction of bits strictly bigger than $1-\alpha$.

Now consider the bit number $m$ of the sequence defined by $f$, starting at the begining of a block. Let $m+n$ be the last position of that block. By hypothesis, among the $m$ first bits (for $m$ large enough), there are at least $m(1-\alpha) - \mathcal{O}(1)$ bits which are guessed correctly by $h'$. In particular, for any $1 \leq i \leq n$, there are also at least $m(1-\alpha) - \mathcal{O}(1)$ bits which are guessed correctly among the $m+i$ first bits. Also for any $1 \leq i \leq n$, the number of total bits is at most $m + n$, which is at most $m + m/c$. Thus for each $i$ the fraction of bits which are guessed correctly before $m+i$ is at least:

As $m$ goes to infinity, this value converges to:

Thus $\gamma(Y) \geq \frac{1-\alpha}{1+1/c}$. We can carry out this argument for $c$ larger and larger, making lower bounds on $\gamma(Y)$ closer and closer to $1-\alpha$. Thus if for any $k$, we can split any $Y$ into blocks of bits as above such that the resulting function is not $2^{\lfloor 2^{n/k} \rfloor}$-i.o.$\alpha$-e., then $\gamma(Y) \geq 1 - \alpha$. By hypothesis we can do this for every $Y$ computable by $X$. Hence $\Gamma(X) \geq 1 - \alpha$. \end{proof}

By contrapositive, if $\Gamma(X) \lt (1-\alpha)$, for $1/2 \lt \alpha \lt 1$, then for some $k \in \omega$, $X$ computes a function which is $2^{\lfloor 2^{n/k} \rfloor}$-i.o.$\alpha$-e. \\

We now need to borrow some technics from the field of error correcting codes. The idea is the folloing: We want to transmit some message of length $m$. But some random bit flip can occur during the transmission. We want to make sure that if the percentage of error is small enough, we can still recover the original message. The idea is to use an injection $\Phi$ from $2^m$ into $2^n$ for some $n \gt \gt m$, in such a way that the elements in the range of $\Phi$, are pairwise far away from each other, in the sense of the hamming distance. If $d$ is the smallest distance between two elements in the range of $\Phi$, then it is clear that we can recover up to $d/2$ error.

Also we would like $n$ to be not much bigger than $m$ (ideally a multiplicative constant). It is easy to find such a multiplicative constant allowing, to have a list of $2^m$ elements of $2^n$, which are all at a distance of at least $1/2 - \epsilon$ from each other, for $\epsilon$ as small as we want. Thus it is possible to correct this way, up to a fraction $1/4$ of error. It is not anymore possible if the fraction is bigger than $1/4$. However, if the fraction is smaller than $1/2$, it is possible to identify a small list of messages, among which must figure our original message. It is even possible to make the size of the list constant. Formally we use the following theorem, for which we provide a proof for completness:

\begin{theorem}[The list decoding capacity theorem] Let $0 \lt \theta \lt 1/2$. There exists $L \in \omega$ and $0 \lt R \lt 1$ as follows.

For any $n$, there exists a set $C$ of $2^{\lfloor Rn \rfloor}$ many strings of length $n$ such that for any string $\s$ of length $n$, there are at most $L$ strings $\tau$ in $C$ such that $d(\s, \tau) \lt \theta$. \end{theorem} \begin{proof} We prove that for parameters $L$ and $R$ well chosen, if we pick at random the strings in $C$, the theorem is true with positive probability.

Let $\beta = 2(1/2 - \theta)^2\log(e)$ and pick $L$ such that $\beta - \frac{1}{L} \gt 0$. Then pick $R$ such that $R \lt \beta - \frac{1}{L}$.\\

Using Chernoff bounds, for any string $\tau$ of length $n$, the measure of the set $\{[\s] : |\s| = n \text{ and } d(\tau, \s) \lt \theta\}$ is bounded by $e^{-2(1/2-\theta)^2n} = 2^{-\beta n}$. Thus, given a string $\s$ the probability that picking a string $\tau$ at random gives $d(\s, \tau) \lt \theta$, is bounded by $2^{- \beta n}$.